﻿#region License
/*

	Copyright (C) 2008 Oliver Charles, Daniel Hollander

	This program is free software: you can redistribute it and/or modify
	it under the terms of the GNU General Public License as published by
	the Free Software Foundation, either version 3 of the License, or
	(at your option) any later version.

	This program is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU General Public License for more details.

	You should have received a copy of the GNU General Public License
	along with this program.  If not, see <http://www.gnu.org/licenses/>.
	
*/
#endregion

using System.Collections.Generic;
using Overload;
using Overload.Collections;

namespace Overload.AI
{
    /// <summary>
    /// Implements an A* path finding algorithm
    /// </summary>
    public sealed class Pathfinder
    {
        #region Private Variables

        private readonly IWorld world;

        #endregion
        #region Constructors

        /// <summary>
        /// Create a new path finder for a specific world
        /// </summary>
        /// <param name="world">The world that this path finder will search</param>
        public Pathfinder(IWorld world)
        {
            this.world = world;
        }

        #endregion
        #region Find Best Path

        /// <summary>
        /// Find the best path between 2 tiles.
        /// </summary>
        /// <remarks>
        /// The best path between 2 points is not necessarily the shortest path. The A* path finding
        /// algorithm, which this path finder uses, defines the best path to be the one with the lowest cost.
        /// Cost is determined by the types of tiles that this path finder will move in to. For instance, it
        /// may be shortest to move the unit through fire, but obviously, this is not the "best" path. Instead,
        /// the path finder will consider the cost of moving through fire, and may instead decide to move around
        /// it.
        /// </remarks>
        /// <param name="source">The starting tile.</param>
        /// <param name="destination">The finishing tile.</param>
        /// <returns>An array of <see cref="ITile"/>s, from start to finish of the best path.</returns>
        public ITile[] FindBestPath(ITile source, ITile destination)
        {
            // Initialize the lists
            List<Node> allNodes = new List<Node>();
            List<Node> closed = new List<Node>();
            PriorityQueue<Node, float> open = new PriorityQueue<Node, float>();

            // Push the start onto the lists
            Node sourceNode = new Node(source);
            open.Enqueue(sourceNode, 0);
            allNodes.Add(sourceNode);

            // Begin pathfinding
            while(open.Count > 0)
            {
                // Retrieve the best node from the open list
                Node current = open.Dequeue();
                closed.Add(current);

                // Is this node the goal?
                if(current.Tile == destination)
                {
                    List<ITile> path = new List<ITile>();
                    while(current != null)
                    {
                        path.Insert(0, current.Tile);
                        current = current.Parent;
                    }
                    return path.ToArray();
                }

                // Consider the nodes sucessors
                ITile[] sucessors = world.GetAdjacentTiles(current.Tile);
                foreach(ITile sucessor in sucessors)
                {
                    Node successorNode = allNodes.Find(delegate(Node n) { return n.Tile == sucessor; });
                    if (successorNode == null)
                    {
                        // We've never encountered this node before, so we make a new one and cache it
                        successorNode = new Node(sucessor);
                        allNodes.Add(successorNode);
                    }

                    // Is it closed (already been here)? If not, lets check it out...
                    if(!closed.Contains(successorNode))
                    {
                        // Is it cheaper to use this path, or was the old one ok?
                        if(!open.Contains(successorNode) || current.G + 1 < successorNode.G)
                        {
                            // Great, it's cheaper to go this way! So, update the node
                            successorNode.Parent = current;
                            successorNode.G = current.G + successorNode.Tile.MovementCost;
                            successorNode.H = world.TileDistance(successorNode.Tile, destination);

                            // We've changed it's F value, so we should check this node out again
                            open.Enqueue(successorNode, -successorNode.Cost);
                        }
                    }
                }
            }

            return null;
        }

        #endregion
    }
}